package com.demo.java.OD451_500.OD472;

import java.util.*;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【路口最短时间问题(C&D卷)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146353938
 */
public class OdMain {
    static final int MAX_SPEED = Integer.MAX_VALUE;

    // 方向枚举，表示上下左右
    enum Direction {UP, RIGHT, DOWN, LEFT}

    static class Point {
        int x, y, direction, speed;

        public Point(int x, int y, int direction, int speed) {
            this.x = x;
            this.y = y;
            this.direction = direction;
            this.speed = speed;
        }
    }

    // 比较器，用于优先队列中的排序
    static class Compare implements Comparator<Point> {
        public int compare(Point a, Point b) {
            return Integer.compare(a.speed, b.speed);
        }
    }

    // 计算从起点到终点的最短时间
    static int calcTime(int[][] lights, int timePerRoad, int rowStart,
                        int colStart, int rowEnd, int colEnd) {
        // 初始化结果数组，存储每个位置和方向的最短时间
        int[][][] result = new int[rowEnd + 1][colEnd + 1][4];
        for (int[][] row : result) {
            for (int[] col : row) {
                Arrays.fill(col, MAX_SPEED);
            }
        }

        // 使用优先队列来进行Dijkstra算法
        PriorityQueue<Point> pq = new PriorityQueue<>(new Compare());
        for (int i = 0; i < 4; i++) {
            pq.add(new Point(rowStart, colStart, i, 0));
        }

        // 方向数组，表示上、右、下、左四个方向
        int[][] directions = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

        // Dijkstra算法主体
        while (!pq.isEmpty()) {
            Point p = pq.poll();

            // 如果当前速度已经大于已有的最短速度，跳过
            if (p.speed > result[p.x][p.y][p.direction]) {
                continue;
            }

            // 遍历四个方向
            for (int i = 0; i < 4; ++i) {
                int newDir = (p.direction + i) % 4;  // 计算新的方向
                int newX = p.x + directions[newDir][0];  // 新的X坐标
                int newY = p.y + directions[newDir][1];  // 新的Y坐标

                // 检查是否越界
                if (newX >= 0 && newX <= rowEnd && newY >= 0 && newY <= colEnd) {
                    // 计算新的速度
                    int newSpeed = p.speed + timePerRoad + (i != 1 ? lights[p.x][p.y] : 0);
                    // 如果新的速度小于当前记录的最短速度，更新最短速度
                    if (newSpeed < result[newX][newY][newDir]) {
                        result[newX][newY][newDir] = newSpeed;
                        pq.add(new Point(newX, newY, newDir, newSpeed));  // 将新的状态加入队列
                    }
                }
            }
        }

        // 返回最短的结果（上、右、下三个方向）
        return Math.min(Math.min(result[rowEnd][colEnd][0], result[rowEnd][colEnd][1]),
                result[rowEnd][colEnd][2]);
    }

    public static void main(String[] args) {
        // 测试用例
        int[][] lights = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};  // 信号灯延时
        int timePerRoad = 60;  // 每条路的通行时间
        int rowStart = 0;  // 起点行
        int colStart = 0;  // 起点列
        int rowEnd = 2;  // 终点行
        int colEnd = 2;  // 终点列

        // 计算并输出最短时间
        System.out.println(calcTime(lights, timePerRoad, rowStart, colStart, rowEnd, colEnd));
    }
}